import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-10
 * Time:11:02
 */
class Node {
    public int val;
    public List<Node> children;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};


public class TestDemo {
    //589. N 叉树的前序遍历
    //给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。
    //n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
    //
    //来源：力扣（LeetCode）
    //链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
    //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    public static List<Integer> preorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.add(root.val);
        for (Node a : root.children) {
            list.addAll(preorder(a));
        }
        return list;
    }
    //查找输入整数二进制中1的个数
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int num = scanner.nextInt();
            int count = 0;
            for (int i = 0; i < 32; i++) {
                if (((num >> i) & 1) == 1) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    //牛客 手套
    /**
     对于非0递增序列(a1 < a2 < a3 < ... < an)如何覆盖每一个种类呢？
     举一个小例子：在2 3 4 5的序列中任意找三个数求和，保证没有其他的三个数的和大于它，你肯定会选择3，4，5；那如果需要找一个整数比其中任意三个数的和都大，且为最小的一个，应该怎么选？
     答案为：（（2 + 3 + 4 + 5）- 2）+ 1 即可保证序列中任取三个数不可能比它大，且为符合条件的最小值。
     覆盖(a1,a2,...an)的数为(sum(a1, a2, ..., an) - a1) + 1;// a1的值为最小值
     1. 题目中存在最差情况为，一边没有，这时候需要将此种颜色所有的手套带走才可以保证题意。
     2. 第二中情况就是上面的例子所体现的情况，在左右两边分别找出能够覆盖全部颜色的最小数量
     3. 判断左右两边那一边需要拿的数量最小就拿那一边，然后在另一边随便拿一个就能保证题意*/
    public static int findMinimum(int n, int[] left, int[] right) {
        int sumLeft = 0;
        int sumRight = 0;
        int sum = 0;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            //  左边或者右边没有的时候需要全部拿走(最差结果)
            if (left[i] == 0 || right[i] == 0) {
                sum = sum + left[i] + right[i];
            } else {
                // 找到左边和右边分别最少的颜色的数量并计算总和
                sumLeft += left[i];
                sumRight += right[i];
                leftMin = Math.min(leftMin, left[i]);
                rightMin = Math.min(rightMin, right[i]);
            }
        }
        //  找到左边和右边中较小的值，在另一边直接拿一个就可以保证题意
        return sum += Math.min(sumLeft - leftMin + 1, sumRight - rightMin + 1) + 1;
    }

    public static void main(String[] args) {
        int n = 4;
        int[] left = {0, 7, 1, 6};
        int[] right = {1, 5, 0, 6};
        System.out.println(findMinimum(4, left, right));
    }
}
